/**
 * SRM 516 Division 2 Level One(250) -- NetworkXZeroOne
 * http://community.topcoder.com/stat?c=problem_statement&pm=11524&rd=14541
 */

package topcoder;

public class NetworkXZeroOne {

	/**
	 * First attempt -- O(2^n)
	 */
	
	private boolean check(String s) {
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i - 1) == s.charAt(i))
				return false;
		}
		return true;
	}

	private String _reconstruct(String s, int i) {
		if (i == s.length()) {
			if (check(s))
				return s;
			else
				return "";
		}
		if (s.charAt(i) == '?') {
			StringBuilder sb = new StringBuilder(s);
			sb.setCharAt(i, 'x');
			String r = _reconstruct(sb.toString(), i + 1);
			if (!r.equals(""))
				return r;
			else {
				sb.setCharAt(i, 'o');
				return _reconstruct(sb.toString(), i + 1);
			}
		} else
			return _reconstruct(s, i + 1);
	}

	public String reconstruct(String message) {
		return _reconstruct(message, 0);
	}

	
	/**
	 * Faster code -- O(n^2)
	 */
	public String reconstruct2(String message) {
		boolean b = false;
		StringBuilder s = new StringBuilder(message);
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) != '?' && !b) {
				for (int j = i - 1; j >= 0; j--) {
					if (s.charAt(j + 1) == 'x')
						s.setCharAt(j, 'o');
					else
						s.setCharAt(j, 'x');
				}
				b = true;
			}
			if (s.charAt(i) == '?' && b) {
				if (s.charAt(i - 1) == 'x')
					s.setCharAt(i, 'o');
				else
					s.setCharAt(i, 'x');
			}
		}
		return s.toString();
	}
}
